
<!DOCTYPE html>
<html>

	<head>
	<title>CAIJL's Blog</title>
	<meta charset="utf-8"/>
	<link rel="stylesheet" href="/font-awesome-4.7.0/css/font-awesome.min.css">

	<link rel="stylesheet" href="/bootstrap-3.3.7/css/bootstrap.min.css">
	<script src="/jquery-2.1.1/jquery.min.js"></script>
	<script src="/bootstrap-3.3.7/js/bootstrap.min.js"></script>

	<link rel="stylesheet" href="/css/bootstrap-slider.min.css">
	<script src="/js/bootstrap-slider.min.js"></script>
	
	<link rel="stylesheet" href="/css/main.css">
	<script src="/js/main.js"></script>
	
	<link rel="stylesheet" href="/css/cursor.css">
	<script src="/js/cursor.js"></script>
	
	
	<link rel="stylesheet" href="/css/code.css">
	<!--link rel="stylesheet" href="/css/markdown.css"-->
	
	<link rel="stylesheet" href="/css/head.css">

	<script src="/js/window.js"></script>
	<script src='//unpkg.com/valine/dist/Valine.min.js'></script>
	</head>
<body>

	<link rel="stylesheet" href="/katex/katex.min.css" crossorigin="anonymous">
	<script src="/katex/katex.min.js" crossorigin="anonymous"></script>
	<script src="/katex/contrib/mathtex-script-type.min.js" defer></script>
	<script defer src="/katex/contrib/auto-render.min.js"crossorigin="anonymous"
	    onload="renderMathInElement(document.body);"></script>
	<script>document.addEventListener("DOMContentLoaded", function() {renderMathInElement(document.body,{"delimiters":[{left: "$", right: "$", display: false}]});});</script>
	<nav class="navbar navbar-default header card" role="navigation" style="width: 100%;">
	<div class="container-fluid"> 
	<div class="navbar-header">
		<button type="button" class="navbar-toggle" data-toggle="collapse"
				data-target="#example-navbar-collapse">
			<span class="icon-bar"></span>
			<span class="icon-bar"></span>
			<span class="icon-bar"></span>
		</button>
		<a class="navbar-brand" href="/"><span><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi mathvariant="bold">C</mi><mi mathvariant="bold">A</mi><mi mathvariant="bold">I</mi><mi mathvariant="bold">J</mi><msup><mi mathvariant="bold">L</mi><mo mathvariant="bold" lspace="0em" rspace="0em">′</mo></msup><mi mathvariant="bold">s</mi><mi mathvariant="bold">B</mi><mi mathvariant="bold">L</mi><mi mathvariant="bold">O</mi><mi mathvariant="bold">G</mi></mrow><annotation encoding="application/x-tex">\mathbf{CAIJL'sBLOG}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height: 0.751892em; vertical-align: 0em;"></span><span class="mord"><span class="mord mathbf">C</span><span class="mord mathbf">A</span><span class="mord mathbf">I</span><span class="mord mathbf">J</span><span class="mord"><span class="mord mathbf">L</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height: 0.751892em;"><span class="" style="top: -3.063em; margin-right: 0.05em;"><span class="pstrut" style="height: 2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathbf mtight">′</span></span></span></span></span></span></span></span></span><span class="mord mathbf">s</span><span class="mord mathbf">B</span><span class="mord mathbf">L</span><span class="mord mathbf">O</span><span class="mord mathbf">G</span></span></span></span></span></span></a>
	</div>
	<div class="collapse navbar-collapse" id="example-navbar-collapse">
		<ul class="nav navbar-nav" style="background-color:#fcfcfc">
			<li><a href="/"><i class="menu-item-icon fa fa-fw fa-home"></i>首页</a></li>
			<li><a href="/archives/"><i class="menu-item-icon fa fa-fw fa-archive"></i>文章</a></li>
			<li><a href="/tags/"><i class="menu-item-icon fa fa-fw fa-tags"></i>标签</a></li>
			<li><a href="/settings/"><i class="menu-item-icon fa fa-fw fa-cogs"></i>设置</a></li>
			<!--li><a href="/about/"><i class="menu-item-icon fa fa-fw fa-user"></i>关于</a></li-->
			<li><a href="/games/"><i class="menu-item-icon fa fa-fw fa-gamepad"></i>其它</a></li>
			

		</ul>
	</div>
	</div>
	</nav>
<div class="container">
	<div style="height: 60px;"></div>
	<div class="row" >
		<div class="col-md-8">
			<div class="panel panel-default card" style="padding: 10px;position: relative;">
                <img src='/img/bg/57.png' style="width:100%"/>
				<span style="position: absolute;left:15px;bottom:15px;width:90%;"><font class="view-text" style="color:#fcfcfc;font-size:25px">分析组合 选读</font><br><a href="/tags/2021/" class="tag"><span  style="background-color: rgb(52, 152, 219);">2021</span></a>&nbsp;<a href="/tags/组合/" class="tag"><span  style="background-color: rgb(231, 76, 60);">组合</span></a>&nbsp;<a href="/tags/笔记/" class="tag"><span  style="background-color: rgb(82, 196, 26);">笔记</span></a></span>
			</div>
			<div class="panel panel-default card" style="padding: 10px;" id="main">
                <p>神 <script type="math/tex">\rm \color{black}x\color{red}\text{义x}</script> 和 <script type="math/tex">\rm \color{black}Z\color{red}LC\_AK</script> 都读完了 </p>
<p>链接在这儿：<a href="https://xyix.gitee.io/images/AnalComb.pdf">膜拜！！！</a></p>
<p><del>如果每天5页是不是6个月就能读完</del></p>
<h1 id="_1">为什么要看这本奇怪的书 <del>（概说）</del></h1>
<blockquote>
<p>ANALYTIC COMBINATORICS is primarily a book about combinatorics, that is, the
study of finite structures built according to a finite set of rules. Analytic in the title means that we concern ourselves with methods from mathematical analysis, in particular complex and asymptotic analysis. The two fields, combinatorial enumeration and complex analysis, are organized into a coherent set of methods for the first time in this book. Our broad objective is to discover how the continuous may help us to understand the discrete and to quantify its properties.</p>
</blockquote>
<h1 id="rm-part-a-smallrm-symbolic-methods">
<script type="math/tex">\rm Part.\ A</script>有符号的计数 <script type="math/tex">\small(\rm SYMBOLIC\ METHODS)</script>
</h1>
<h2 id="bf-i-smallrm-combinatorial-structures-and-ordinary-generating-functions">
<script type="math/tex">\bf I</script> 组合结构与普通生成函数 <script type="math/tex">\small(\rm Combinatorial\ Structures\ and\ Ordinary\ Generating\ Functions)</script>
</h2>
<h3 id="mathbfi1-smallrm-symbolic-enumeration-methods">
<script type="math/tex">\mathbf{I}.1</script> 有符号的枚举方法 <script type="math/tex">\small\rm (Symbolic\ enumeration\ methods)</script>
</h3>
<p>首先，组合数学处理的是 <strong>离散对象</strong><script type="math/tex">(\rm discrete\ objects)</script>。换句话说，对象必须能用有限的规则描述得到。比如排列就可以认为是离散对象，因为可以用有限的规则描述。</p>
<p><strong>定义 <script type="math/tex">\mathrm I.1</script></strong>:一个<strong>组合类</strong>（简称<strong>类</strong>），是一个集合，在其上定义一个 <strong>大小函数</strong>，需要满足一下条件：</p>
<ol>
<li>每个<strong>元素</strong><script type="math/tex">(\rm element)</script>的大小是非负的</li>
<li>对于任意一个大小的元素，数量是有限的</li>
</ol>
<p>如果一个类 <script type="math/tex">\mathcal{A}</script> ，有元素 <script type="math/tex">\alpha\in\mathcal{A}</script> 的大小表示为 <script type="math/tex">|\alpha|</script>，也记为 <script type="math/tex">|\alpha|_{\mathcal{A}}</script> 。两者并没有太大的区别，除非有毒瘤的情况要区分类。记 <script type="math/tex">\mathcal{A}_n</script> 为 <script type="math/tex">\mathcal A</script> 中大小为 <script type="math/tex">n</script> 的元素组成的集合。我们记 <script type="math/tex">A_n=\operatorname{card}(\mathcal{A}_n)</script> （应该也可以记为 <script type="math/tex">a_n=A_n=|\mathcal A_n|</script>）。</p>
<p>一个组合类是一个二元组 <script type="math/tex">(\mathcal A,|\cdot|)</script>。 <script type="math/tex">\mathcal A</script> 可数，<script type="math/tex">|\cdot|</script> 是一个映射 <script type="math/tex">|\cdot|\coloneqq A\mapsto \mathbb{N}</script> 。不过正如上面强调的一样，仍然要求有限。</p>
<p><strong>定义 <script type="math/tex">\mathrm I.2</script></strong>：一个类的 <strong>计数序列</strong><script type="math/tex">(\rm counting\ sequence)</script> 是一个整数序列 <script type="math/tex">(A_n)_{n\ge 0}</script>，换句话说就是这么一个东西 <script type="math/tex">(|\mathcal{A}_0|,|\mathcal{A}_1|,|\mathcal{A}_2|,\ldots)</script>。</p>
<hr>
<ul>
<li>例题 <script type="math/tex">\mathbf I.1</script>
</li>
</ul>
<p><strong>二进制字符串</strong>。考虑 <script type="math/tex">\mathcal{W}</script> 是所有二进制字符串构成的集合，每个单词的任何一位都取自基础字母集 <script type="math/tex">\mathcal{A}={0,1}</script>，<script type="math/tex">\mathcal{W}</script> 大概长这样：
<script type="math/tex; mode=display">
\mathcal{W}\coloneqq\{\epsilon,0,1,00,01,10,11,000,001,010,\ldots\}
</script>
式中的 <script type="math/tex">\epsilon</script> 指的是空字符串。容易知道 <script type="math/tex">\mathcal{W}</script> 的计数序列 <script type="math/tex">(W_n)</script> 满足
<script type="math/tex; mode=display">
W_n=2^n
</script>
</p>
<hr>
<ul>
<li>例题 <script type="math/tex">\mathbf I.2</script>
</li>
</ul>
<p><strong>排列</strong>。一个长度为 <script type="math/tex">n</script> 的排列本质是一个在整数区间 <script type="math/tex">\mathcal{I}_n\coloneqq [1,\ldots,n]</script> 的双射，因此可以用数组表示：
<script type="math/tex; mode=display">
\begin{pmatrix}
1&2&\ldots&n\\
\sigma_1&\sigma_2&\ldots&\sigma_n
\end{pmatrix}
</script>
用 <script type="math/tex">\sigma_1\sigma_2\ldots\sigma_n</script>就可以描述一个排列，其集合 <script type="math/tex">\mathcal{P}</script> 长这样：
<script type="math/tex; mode=display">
\mathcal{P}\coloneqq\{1,12,21,123,132,213,231,321,312,\ldots,12345,\ldots\}
</script>
也不难发现 <script type="math/tex">P_n</script> 满足：
<script type="math/tex; mode=display">
P_n=n!
</script>
</p>
<hr>
<ul>
<li>例题 <script type="math/tex">\mathbf I.3</script>
</li>
</ul>
<p><strong>剖分</strong>（凸多边形三角划分）。先上一张嫖来的图：</p>
<p><img alt="" src="/img/2ezm2lqm.png"></p>
<p>定义一个类 <script type="math/tex">\mathcal{T}</script> 是凸多边形的三角形划分，三角形不能重合。定义一个元素 <script type="math/tex">a</script> 的大小为其三角形的数量（即边数减二）。画图可以发现一个凸四边形由两种方法分成两个三角形，而凸五边形有五种分发。比较小的计数序列得到比较简单：
<script type="math/tex; mode=display">
T_1=1,T_1=1,T_2=2,T_3=5,T_4=14,T_5=42,\ldots
</script>
这个的通项就不像前两种一样显然了，好在一些牛逼的人已经给了我们答案：
<script type="math/tex; mode=display">
\tag{1}T_n=\frac1{n+1}\binom{2n}n
</script>
Euler 说，这个计数最好用生成函数来推到，这里就直接贴<a href="https://chen-jia-liang.gitee.io/article/How_to_Count.html#3">链接</a>了</p>
<p>原书这里用了一页来讲述卡特兰数的故事，这里 <script type="math/tex">\rm skip</script> 了（逃</p>
<hr>
<p>尽管前面的例子非常简单，但在遇到组合枚举问题时，确定计数序列的初始值通常是一个好主意，可以用手，也可以更好地利用计算机。 <del>也就是鼓励打表</del></p>
<table>
<thead>
<tr>
<th>
<script type="math/tex">n</script>
</th>
<th align="right">
<script type="math/tex">0</script>
</th>
<th align="right">
<script type="math/tex">1</script>
</th>
<th align="right">
<script type="math/tex">2</script>
</th>
<th align="right">
<script type="math/tex">3</script>
</th>
<th align="right">
<script type="math/tex">4</script>
</th>
<th align="right">
<script type="math/tex">5</script>
</th>
<th align="right">
<script type="math/tex">6</script>
</th>
<th align="right">
<script type="math/tex">7</script>
</th>
<th align="right">
<script type="math/tex">8</script>
</th>
<th align="right">
<script type="math/tex">9</script>
</th>
<th align="right">
<script type="math/tex">10</script>
</th>
</tr>
</thead>
<tbody>
<tr>
<td>
<script type="math/tex">W_n</script>
</td>
<td align="right">
<script type="math/tex">1</script>
</td>
<td align="right">
<script type="math/tex">2</script>
</td>
<td align="right">
<script type="math/tex">4</script>
</td>
<td align="right">
<script type="math/tex">8</script>
</td>
<td align="right">
<script type="math/tex">16</script>
</td>
<td align="right">
<script type="math/tex">32</script>
</td>
<td align="right">
<script type="math/tex">64</script>
</td>
<td align="right">
<script type="math/tex">128</script>
</td>
<td align="right">
<script type="math/tex">256</script>
</td>
<td align="right">
<script type="math/tex">512</script>
</td>
<td align="right">
<script type="math/tex">1024</script>
</td>
</tr>
<tr>
<td>
<script type="math/tex">P_n</script>
</td>
<td align="right">
<script type="math/tex">1</script>
</td>
<td align="right">
<script type="math/tex">1</script>
</td>
<td align="right">
<script type="math/tex">2</script>
</td>
<td align="right">
<script type="math/tex">6</script>
</td>
<td align="right">
<script type="math/tex">24</script>
</td>
<td align="right">
<script type="math/tex">120</script>
</td>
<td align="right">
<script type="math/tex">720</script>
</td>
<td align="right">
<script type="math/tex">5040</script>
</td>
<td align="right">
<script type="math/tex">40320</script>
</td>
<td align="right">
<script type="math/tex">362880</script>
</td>
<td align="right">
<script type="math/tex">3628800</script>
</td>
</tr>
<tr>
<td>
<script type="math/tex">T_n</script>
</td>
<td align="right">
<script type="math/tex">1</script>
</td>
<td align="right">
<script type="math/tex">1</script>
</td>
<td align="right">
<script type="math/tex">2</script>
</td>
<td align="right">
<script type="math/tex">5</script>
</td>
<td align="right">
<script type="math/tex">14</script>
</td>
<td align="right">
<script type="math/tex">42</script>
</td>
<td align="right">
<script type="math/tex">132</script>
</td>
<td align="right">
<script type="math/tex">429</script>
</td>
<td align="right">
<script type="math/tex">1430</script>
</td>
<td align="right">
<script type="math/tex">4862</script>
</td>
<td align="right">
<script type="math/tex">16796</script>
</td>
</tr>
</tbody>
</table>
<p>
<script type="math/tex; mode=display">\tag{2}{\text{}}</script>
</p>
<p>一张表格可能会帮助我们了解公式。比如 <script type="math/tex">(1)</script> 并不是特别容易得到，但我们可以拆分 <script type="math/tex">T_{40}</script>
</p>
<p>
<script type="math/tex; mode=display">
T_{40}=2^2\cdot 5\cdot7\cdot11\cdot23\cdot43\cdot47\cdot53\cdot59\cdot61\cdot67\cdot71\cdot73\cdot79
</script>
</p>
<p>这可以帮助我们想到公式。值得一提的是，这些数列都可以在 <a href="https://oeis.org/"><script type="math/tex">\mathbf{OEIS}</script></a> 上找到。</p>
<p>来两个使用 <script type="math/tex">\mathbf{OEIS}</script> 的例题。</p>
<blockquote>
<p>
<script type="math/tex">\mathbf I.1</script>
<strong>项链</strong>。用 <script type="math/tex">n</script> 颗珠子最多有多少种项链设计，每颗珠子可以为黑或白。手玩一下就可以得到这个集合 <script type="math/tex">\mathcal N</script> 的计数序列的前几项：
<script type="math/tex; mode=display">N_1=2,N_2=3,N_3=4,N_4=6,N_5=8,N_6=14,N_7=20\ldots</script>
于是就搜索到了这个<a href="https://oeis.org/A000031">序列</a></p>
<p>
<script type="math/tex">\mathbf I.2</script>
<strong>单峰排列</strong>。对于一个排列使得 <script type="math/tex">a_1<a_2<a_3<\ldots<a_k>a_{k+1}>a_{k+2}>\ldots>a_n</script> 则称其为单峰排列。记 <script type="math/tex">\mathcal{U}</script> 单峰排列的类，如果记排列 <script type="math/tex">u</script> 的大小为其的长度 <script type="math/tex">-1</script>，简单打表发现 <script type="math/tex">U_n=2^n</script>
</p>
</blockquote>
<p>不过最好还是严格证明的说</p>
<p>值得注意的是，单词和排列可以使用朴素地计数原理。如果有 有限集 <script type="math/tex">\mathcal B</script> 和 <script type="math/tex">\mathcal C</script>，就会有：</p>
<p>
<script type="math/tex; mode=display">
\tag{3}{\begin{cases}\operatorname{card}(\mathcal B\cup \mathcal C)=\operatorname{card}(\mathcal B)+\operatorname{card}(\mathcal C)\ (\mathrm{provided} \mathcal B\cap \mathcal C=\varnothing)\\ \operatorname{card}(\mathcal B\times \mathcal C)=\operatorname{card}(\mathcal B)\cdot \operatorname{card}(\mathcal C)\end{cases}}
</script>
</p>
<p>这些原则我们很快就会用到。接下来，为了组合枚举，我们希望能确认两个组合类是否仅仅是变体。</p>
<p><strong>定义</strong><script type="math/tex">\mathrm I.3</script>：两个组合类 <script type="math/tex">\mathcal A</script> 和 <script type="math/tex">\mathcal B</script> 被认为是同构的，写成 <script type="math/tex">\mathcal A\cong \mathcal B</script>，当且仅当他们的计数序列相同。这个条件等价于一个<script type="math/tex">\mathcal A\Longleftrightarrow \mathcal B</script>双射的存在。可以称 <script type="math/tex">\mathcal A,\mathcal B</script>双射等价 <script type="math/tex">(\rm bijectively\ equivalent)</script>。我们一般识别同构类用一个简单的等号 <script type="math/tex">(\mathcal A=\mathcal B)</script>，但一些并不这么简单的组合同构，用的是 <script type="math/tex">\mathcal A\cong \mathcal B</script>。 <del>机翻：我们将符号<script type="math/tex">\mathcal A\cong \mathcal B</script>限制在组合同构由一些非平凡变换产生的应力情况下。</del></p>
<p>举个例子，<script type="math/tex">\mathcal{U}</script> 与 <script type="math/tex">\mathcal{W}</script> 就是同构的，这两个类就有双射。如果有一个大小为 <script type="math/tex">n</script> 的 <script type="math/tex">w\in\mathcal{W}</script> ，给它表上下标，把为 <script type="math/tex">1</script> 位置对应的下标放在 <script type="math/tex">n+1</script> 前，其他放在 <script type="math/tex">n+1</script> 后，就得到了一个对应的 <script type="math/tex">u\in\mathcal{U}</script>。于是 <script type="math/tex">\mathcal{U}\cong \mathcal{W}</script>。</p>
<p><strong>定义 <script type="math/tex">\mathrm I.4</script></strong>：计数序列 <script type="math/tex">A_n</script> 的普通生成函数 <script type="math/tex">(\rm ordinary\ generating\ function,\mathbf{OGF})</script>：</p>
<p>
<script type="math/tex; mode=display">
\tag{7}{A(z)=\sum_{n=0}^\infty A_nz^n}
</script>
</p>
<p>对于一个组合类 <script type="math/tex">\mathcal A</script>，其生成函数有更优美（？）的定义：</p>
<p>
<script type="math/tex; mode=display">
\tag{8}{A(z)=\sum_{\alpha\in \mathcal A}z^{|\alpha|}}
</script>
</p>
<p>这里称 <script type="math/tex">z</script> 为一个标记变量来区分大小。所有的大小为 <script type="math/tex">n</script> 的对象都会使 <script type="math/tex">z^n</script> 的系数加一。我们也把它称为 <strong>形式幂级数</strong><script type="math/tex">(\rm formal\ power\ series)</script>
</p>
<p><strong>命名约定</strong>：有这样的约定，一个类、计数序列和生成函数用同一个字母表示。如 <script type="math/tex">\mathcal A</script> 表示一个类，<script type="math/tex">\{A_n\}</script> 或 <script type="math/tex">(A_n)</script> 表示他的计数序列，而 <script type="math/tex">A(z)</script> 或 <script type="math/tex">a(z)</script> 是他的生成函数。</p>
<p><strong>系数提取</strong>：我们将提取 <script type="math/tex">f(z)</script> 的 <script type="math/tex">z^n</script> 系数记为 <script type="math/tex">[z^n]f(z)</script>。如果有一个形式幂级数 <script type="math/tex">f(z)=\sum f_nz^n</script>：
<script type="math/tex; mode=display">
\tag{9}{[z^n]\left(\sum_{n\ge 0}f_nz^n\right)}=f_n
</script>
</p>
<p>我们刚刚的三个例子都可以写成 <script type="math/tex">\mathbf{OGF}</script> 的形式
<script type="math/tex; mode=display">
\begin{cases}
W(z)&=\sum\limits_{n=0}^\infty2^nz^n=\dfrac1{1-2z}\\
P(z)&=\sum\limits_{n=0}^\infty n!z^n\\
T(z)&=\sum\limits_{n=0}^\infty \dfrac1{n+1}\dbinom{2n}n=\dfrac{1-\sqrt{1-4z}}{2z}
\end{cases}
</script>
级数 <script type="math/tex">W(z)</script> 与 <script type="math/tex">T(z)</script> 都是 <strong>标准分析对象</strong><script type="math/tex">(\rm standard\ analytic\ objects)</script>。我们可以在复数域 <script type="math/tex">\mathbb C</script> 中为形式变量 <script type="math/tex">z</script>。事实上，<script type="math/tex">W(z)</script> 收敛需要 <script type="math/tex">|z|<\frac12</script>， <script type="math/tex">T(z)</script> 收敛需要 <script type="math/tex">|z|<\frac14</script>。不过 <script type="math/tex">P(z)</script> 收敛半径为 <script type="math/tex">0</script>，当且仅当 <script type="math/tex">z=0</script> 时 <script type="math/tex">P(z)=1</script>。</p>
<p>
<script type="math/tex">\rm\color{black}Z\color{red}LC\_AK</script>：形式幂级数不用管收敛性，不过在我们小学二年级中学过的 《高等数学》《微积分》中的运算都是要考虑收敛性的。</p>
<p><del>经过严格的证明</del>，形式幂级数也适用常规的运算。</p>
<p><strong>生成函数的组合形式</strong>：生成函数其实是对一个类的 <strong>降维打击</strong>，生成函数已经把一个组合类的内部结构破坏掉了。这么说可能有点玄乎，不过可能看完下面两个例子就会有更深的理解。</p>
<hr>
<p><img alt="嫖图" src="/img/dki140qy.png"></p>
<p>这里有一个长长的大分子，结构十分复杂。但我们在生成函数中只用 <script type="math/tex">z^{26}</script> 就能表示它了。</p>
<hr>
<p><img alt="嫖图" src="/img/0h1dm8d9.png"></p>
<p>
<script type="math/tex">\mathcal H</script> 是一个组合类，里面有一些奇形怪状的东西。但如果把顶点替换为 <script type="math/tex">z</script>，那么生成函数十分简单：<script type="math/tex">H(z)=z+z^2+2z^3+3z^4</script>。图的结构信息已经完全损失了。</p>
<p>如果把一个图的边替换成 <script type="math/tex">y</script>，那么会得到另一个生成函数 <script type="math/tex">H(z)=1+y+y^2+2y^3+y^4+y^6</script>。甚至可以同时换边和点得到一个二元生成函数 <script type="math/tex">(\rm bivariate\ generating\ function)</script>。<script type="math/tex">H(z,y)=z+z^2y+z^3y^2+z^3y^3+z^4y^3+z^4y^4+z^4y^6</script>。不过多元生成函数已经是后话了。</p>
<hr>
<p>把组合类变成生成函数就会完全丢失原来的结构信息，可以构造很多组合类拥有相同的生成函数。</p>
<p>在生活中，一些组合结构往往可以由更简单的组合结构组成。</p>
<p>组合结构的类是通过更基本的类的直接构造而成。</p>
<p><strong>定义 <script type="math/tex">\mathrm I.5</script></strong>：<script type="math/tex">\Phi</script> 是一个 <script type="math/tex">m</script> 进制结构，由任何相关联的 <script type="math/tex">\mathcal{B}^{(1)},\ldots,\mathcal{B}^{(m)}</script>。
<script type="math/tex; mode=display">
\mathcal{A}=\Phi[\mathcal{B}^{(1)},\ldots,\mathcal{B}^{(m)}]
</script>
如果 <script type="math/tex">\mathcal A</script> 的计数序列仅与 <script type="math/tex">\mathcal{B}^{(1)},\ldots,\mathcal{B}^{(m)}</script>的计数序列 <script type="math/tex">B^{(1)},\ldots,B^{(m)}</script> 有关，那么称 <script type="math/tex">\Phi</script> 是可允许的。对于这么一个结构，就会存在一个操作 <script type="math/tex">\Psi</script> 作用于对应的生成函数：
<script type="math/tex; mode=display">
A(z)=\Psi[B^{(1)}(z),\ldots,B^{(m)}(z)]
</script>
于是就出现了玄妙重重的笛卡尔积：</p>
<p><strong>定义 <script type="math/tex">\mathrm I.6</script></strong>：有两个类 <script type="math/tex">\mathcal{B},\mathcal{C}</script>，笛卡尔积是一个二元运算得到一个新的组合类：
<script type="math/tex; mode=display">
\tag{11}{\mathcal{A}=\mathcal{B}\times\mathcal{C}\Longleftrightarrow \mathcal{A}=\{\alpha=(\beta,\gamma)|\beta\in \mathcal{B},\gamma\in\mathcal{C}\}}
</script>
此时的 <script type="math/tex">\alpha=(\beta,\gamma)</script>，应该要满足：
<script type="math/tex; mode=display">
\tag{12}{|\alpha|_{\mathcal{A}}=|\beta|_{\mathcal{B}}}+|\gamma|_{\mathcal{C}}
</script>
这样的形式引导我们将计数序列写成卷积的形式：
<script type="math/tex; mode=display">
\tag{13}{A_n=\sum_{k=0}^nB_kC_{n-k}}
</script>
众所周知加法卷积可以写成多项式乘法的形式：
<script type="math/tex; mode=display">
\tag{14}{A(z)=B(z)\cdot C(z)}
</script>
总结:笛卡尔积与 <script type="math/tex">\mathbf{OGF}</script> 有密不可分的关系。</p>
<p>同样的，如果有组合类 <script type="math/tex">\mathcal A,\mathcal B,\mathcal C</script>，假如：
<script type="math/tex; mode=display">
\tag{15}{\mathcal{A}=\mathcal{B}\cup \mathcal{C}},\mathrm{with}\ \mathcal{B}\cap \mathcal{C}=\varnothing
</script>
</p>
<p>并且对大小也有要求：
<script type="math/tex; mode=display">
\tag{16}{\forall \omega\in\mathcal{A},|\omega|_{\mathcal{A}}}=\begin{cases}|\omega|_{\mathcal{B}},\omega\in\mathcal{B}\\|\omega|_{\mathcal{C}},\omega\in \mathcal{C}\end{cases}
</script>
就会有：
<script type="math/tex; mode=display">
\tag{17}{A_n=B_n+C_n}
</script>
写成生成函数就会有：
<script type="math/tex; mode=display">
\tag{18}{A(z)=B(z)+C(z)}
</script>
于是总结一下笛卡尔积与 <script type="math/tex">\mathbf{OGF}</script>：
<script type="math/tex; mode=display">
\tag{19}{\begin{cases}
\mathcal{A}=\mathcal{B}\cup\mathcal{C}\Longrightarrow A(z)=B(z)+C(z)\ (\mathrm{provided}\ \mathcal{B}\cap\mathcal{C}=\varnothing)\\
\mathcal{A}=\mathcal{B}\times\mathcal{C}\Longrightarrow A(z)=B(z)\cdot C(z)
\end{cases}}
</script>
相比于 <script type="math/tex">(3)</script> 中简单的规则与 <script type="math/tex">(13)</script> 和 <script type="math/tex">(17)</script> 中的系数，这样的方法更加优美。原书中认为这是组合枚举符号计数的精髓所在。</p>
<h3 id="mathbfi2-smallrm-admissible-constructions-and-specifications">
<script type="math/tex">\mathbf{I}.2</script> 容许结构和规范 <script type="math/tex">\small(\rm Admissible\ constructions\ and\ specifications)</script>
</h3>
<p>本节的主要目的是正式介绍构成组合结构规范语言核心的基本结构。这个核心是基于不相交联合，也称组合和，比如我们刚刚讨论的笛卡尔积。我们也将要进行一些扩展。</p>
<h4 id="mathbfi21-smallrm-basic-constructions">
<script type="math/tex">\mathbf{I}.2.1</script> 基本构造 <script type="math/tex">\small(\rm Basic\ constructions)</script>
</h4>
<p>首先我们给出一个<strong>中立类</strong><script type="math/tex">(\rm neutral\ class)</script>
<script type="math/tex">\mathcal{E}</script>，它由一个大小为 <script type="math/tex">0</script> 的对象组成。大小为 <script type="math/tex">0</script> 的对象称之为 <strong>中立对象</strong><script type="math/tex">(\rm neutral\ object)</script>，写作 <script type="math/tex">\epsilon</script> 或 <script type="math/tex">1</script>。若考虑同构，中立类可以与单位元类比：
<script type="math/tex; mode=display">
\mathcal A\cong \mathcal A\times \mathcal{E}\cong \mathcal{E}\times\mathcal A
</script>
我们引入 <strong>原子类</strong><script type="math/tex">(\rm atomic\ class)</script>，<script type="math/tex">\mathcal Z</script>，其包含一个大小为 <script type="math/tex">1</script> 的元素。一般情况可以用圆<script type="math/tex">(\bullet\ \mathrm{or}\ \circ)</script> 表示，也可以用下标区分。比如 <script type="math/tex">\mathcal{Z}_a=\{a\}</script>,<script type="math/tex">\mathcal{Z}_b=\{b\}</script> (<script type="math/tex">a,b</script> 都是大小为 <script type="math/tex">1</script> 的对象),或以 <script type="math/tex">\mathcal{Z}_{\bullet}=\{\bullet\}</script>,<script type="math/tex">\mathcal{Z}_\circ=\{\circ\}</script> 来构建一颗节点为黑或白的树。</p>
<p>同样的，我们可以写出以 <script type="math/tex">\Box,\epsilon_1,\epsilon_2</script> 为中立对象的中立类 <script type="math/tex">\mathcal{E}_{\Box},\mathcal{E}_1,\mathcal{E}_2</script>。</p>
<p>我们还知道，中立类 <script type="math/tex">\mathcal{E}</script> 与原子类 <script type="math/tex">\mathcal Z</script>的生成函数：
<script type="math/tex; mode=display">
E(z)=1,Z(z)=z
</script>
分别对应生成函数单元 <script type="math/tex">1</script> 和变量 <script type="math/tex">z</script>。</p>
<h5 id="smallrm-combinatorial-sum">组合和 <script type="math/tex">\small(\rm Combinatorial\ sum)</script>
</h5>
<p>也称为 <strong>不相交并集</strong> <script type="math/tex">\rm(disjoint\ union)</script>。</p>
<p>给定两个类 <script type="math/tex">\mathcal B</script> 和 <script type="math/tex">\mathcal C</script>（在标准的集合意义上），我们把用两个不同的颜色 <script type="math/tex">\Box</script> 和 <script type="math/tex">\Diamond</script> 重新为 <script type="math/tex">\mathcal B</script> 和 <script type="math/tex">\mathcal C</script> 染色得到两个副本 <script type="math/tex">B^{\Box}</script> 和 <script type="math/tex">C^{\Diamond}</script>。对于 <script type="math/tex">\Box</script> 和 <script type="math/tex">\Diamond</script> 都有一个中立类。因此定义不相交并 <script type="math/tex">\mathcal B+\mathcal C</script> 定义为它们的 <strong>标准理论并集</strong> <script type="math/tex">(\rm standard\ set-theoretic\ union)</script>
<script type="math/tex; mode=display">
\mathcal B+\mathcal C\coloneqq (\{\Box\}\times \mathcal B)\cup(\{\Diamond\}\times\mathcal C)
</script>
在不相交并集中，对象的大小就是其在原类中的大小，就像在 <script type="math/tex">(16)</script> 中所展示的。当不相交并集运用于不相交集时，和标准的并集是等价的。在下面的讨论中，不论两个集合是否相交，其组合和都是有定义的。于是就有了下面的定义：
<script type="math/tex; mode=display">
\mathcal A=\mathcal B+\mathcal C\Longrightarrow A_n=B_n+C_n\Longrightarrow A(z)=B(z)+C(z)
</script>
不过值得注意的是，标准理论并集不可接受当：
<script type="math/tex; mode=display">
\mathrm{card}(\mathcal B_n\cup \mathcal C_n)=\mathrm{card}(\mathcal B_n)+\mathrm{card}(\mathcal C_n)-\mathrm{card}(\mathcal B_n\cap \mathcal C_n)
</script>
为了能够知道它们的并集，我们还需要知道 <script type="math/tex">\mathcal{B}</script> 和 <script type="math/tex">\mathcal C</script> 内部的结构信息（即它们相交的性质）。</p>
<h5 id="smallrm-cartesian-produc">笛卡尔积 <script type="math/tex">\small\rm (Cartesian\ produc)</script>
</h5>
<p>结构 <script type="math/tex">\mathcal B</script> 和 <script type="math/tex">\mathcal C</script> 形成的所有有序对，大小的定义参见 <script type="math/tex">(12)</script>。</p>
<h5 id="smallrmsequence-construction">序列构造 <script type="math/tex">\small\rm(Sequence\ construction)</script>
</h5>
<p>如果 <script type="math/tex">\mathcal B</script> 是一个类，那么序列类 <script type="math/tex">\mathrm{SEQ}(\mathcal B)</script> 被定义为无限的和：
<script type="math/tex; mode=display">
\mathrm{SEQ}(\mathrm{B})=\{\epsilon\}+\mathcal B+(\mathcal B\times\mathcal B)+(\mathcal B\times\mathcal B\times\mathcal B)+\ldots
</script>
<script type="math/tex">\epsilon</script> 是一个中立类。换句话说：
<script type="math/tex; mode=display">
\mathcal A=\{(\beta_1,\ldots,\beta_{ℓ})|ℓ\ge0,\beta_j\in\mathcal B\}
</script>
需要满足 <script type="math/tex">\mathcal B</script> 不含有中立类，并且大小是可加的，即：
<script type="math/tex; mode=display">
\alpha=(\beta_1,\ldots,\beta_{ℓ})\Longrightarrow|\alpha|=|\beta_1|+\ldots+|\beta_{ℓ}|
</script>
</p>
<h5 id="smallrmcycle-construction">环构造 <script type="math/tex">\small\rm(Cycle\ construction)</script>
</h5>
<p>一个数列转转转就形成了 <strong>环</strong>，符号为 <script type="math/tex">\mathrm{CYC}(\mathcal B)</script>，定义如下：
<script type="math/tex; mode=display">
\mathrm{CYC}(\mathcal{B})\coloneqq(\mathrm{SEQ}(\mathcal B)/\{\epsilon\})/\mathbf{S}
</script>
<script type="math/tex">\mathbf S</script> 是序列间的<strong>等价关系</strong><script type="math/tex">\rm(equivalence\ relation)</script>。定义为：
<script type="math/tex; mode=display">
(\beta_1,\ldots,\beta_r)\mathbf{S}(\beta_1^\prime,\ldots,\beta_r^\prime)
</script>
当且仅当存在一个 <strong>环形平移</strong> <script type="math/tex">(\rm circular\ shif)</script>
<script type="math/tex">\tau</script> 使得 <script type="math/tex">\forall j,\beta_j^\prime=\beta_{\tau(j)}</script>。</p>
<p>用人话说就是两个环可以旋转得到，或者是群论中的同构。举个例子，用 <script type="math/tex">(a,b)</script> 组成的环就会出现同构：
<script type="math/tex; mode=display">
\tag{20}{
    \text{3-cycles}:\begin{cases}
        aaa\\
        aab\ aba\ baa\\
        abb\ bba\ bab\\
        bbb
    \end{cases}
    \text{4-cycle}:\begin{cases}
        aaaa\\
        aaab\ aaba\ abaa\ baaa\\
        aabb\ abba\ bbaa\ baab\\
        abab\ baba\\
        abbb\ bbba\ bbab\ babb\\
        bbbb
    \end{cases}
}
</script>
不言而喻，多个序列可能只对应一个环。</p>
<p>根据定义，这种结构对应于无标号有向环。但后面也可以用于有标号。</p>
<h5 id="small-rmmultiset-construction">多重集构造 <script type="math/tex">\small \rm(Multiset\ construction)</script>
</h5>
<p>多重集可以和序列进行类比，但没有顺序。<script type="math/tex">\mathcal A=\mathrm{MSET}(\mathcal B)</script>
<script type="math/tex">\mathcal{B}</script> 里面所有元素构成的有限集。准确的定义是一个商式：
<script type="math/tex; mode=display">
\mathrm{MSET}(\mathcal B)\coloneqq\mathrm{SEQ}(\mathcal{B}) /\mathbf{R}
</script>
<script type="math/tex">\mathbf{R}</script> 也是序列间的等价关系，我们记 <script type="math/tex">(\alpha_1,\ldots,\alpha_r)\mathbf{R}(\beta_1,\ldots,\beta_r)</script> 当且仅当存在排列 <script type="math/tex">\tau</script> 使得 <script type="math/tex">\beta_j=\alpha_{\tau(j)}</script>，即两个序列可以重排得到。</p>
<h5 id="smallrm-powerset-construction">幂集构造 <script type="math/tex">\small(\rm Powerset\ construction)</script>
</h5>
<p>幂集类 <script type="math/tex">\mathcal A=\mathrm{PSET}(\mathcal B)</script> 被定义为 <script type="math/tex">\mathcal B</script> 的所有有限子集构成的类。</p>
<h5 id="_2">后记</h5>
<blockquote>
<p>
<script type="math/tex">\mathbf{I}.4</script> 组合类的<strong>半环</strong><script type="math/tex">\rm(semi-ring)</script>。半环是去掉+操作中逆元特性的环，有两种运算 <script type="math/tex">+,\times</script>，对于 <script type="math/tex">+,\times</script> 有结合性和幺元，比如：<script type="math/tex">\mathcal{A}+(\mathcal{B}+\mathcal{C})=(\mathcal{A}+\mathcal{B})+\mathcal{C}</script>，<script type="math/tex">\mathcal{A}\times(\mathcal{B}\times\mathcal{C})=(\mathcal{A}\times\mathcal{B})\times\mathcal{C}</script>。还满足分配率：<script type="math/tex">\mathcal{A}\times(\mathcal B+\mathcal C)=\mathcal A\times\mathcal B+\mathcal A\times\mathcal C</script>。</p>
<p>
<script type="math/tex">\mathbf I.5</script> 自然数字 <script type="math/tex">\rm(Natural\ numbers)</script>。定义原子类 <script type="math/tex">\mathcal Z\coloneqq\{\bullet\}</script>。<script type="math/tex">\mathcal I=\mathrm{SEQ}(\mathcal{Z})/\{\epsilon\}</script> 就可以表示所有正整数：<script type="math/tex">\mathcal I=\{\bullet,\bullet\bullet,\bullet\bullet\bullet,\ldots\}</script>。<script type="math/tex">\mathcal I</script> 的 <script type="math/tex">\bf OGF</script> 满足：<script type="math/tex">I(z)=z/(1-z)=z+z^2+z^3+\ldots</script>
</p>
<p>
<script type="math/tex">\mathbf I.6</script> 有间隔地覆盖 <script type="math/tex">\rm(Interval\ coverings)</script>。让 <script type="math/tex">\mathcal Z\coloneqq\{\bullet\}</script>，<script type="math/tex">\mathcal{A}=\mathcal Z+(\mathcal Z\times\mathcal Z)</script>。<script type="math/tex">\mathcal{A}</script> 中有两个元素 <script type="math/tex">\bullet</script> 和 <script type="math/tex">(\bullet,\bullet)</script>。分别画成 <script type="math/tex">\bullet</script> 和 <script type="math/tex">\bullet\!-\!\bullet</script>。那么 <script type="math/tex">\mathcal C=\mathrm{SEQ}(A)</script> 就应该长这样：
<script type="math/tex; mode=display">\bullet,\bullet\ \bullet,\bullet\!-\!\bullet,\bullet\ \bullet\ \bullet,\bullet\!-\!\bullet\ \bullet,\ldots</script>
敏感一点一眼就能看出是斐波那契。因为大小为 <script type="math/tex">n</script> 的元素在 <script type="math/tex">\mathcal{C}=\mathrm{SEQ}(\mathcal Z+(\mathcal Z\times\mathcal Z))</script> 中就相当于用长度为 <script type="math/tex">1</script> 或 <script type="math/tex">2</script> 将 <script type="math/tex">[0,n]</script> 覆盖。</p>
</blockquote>
<h4 id="mathbf-i22-smallrm-the-admissibility-theorem-for-ordinary-generating-functions">
<script type="math/tex">\mathbf I.2.2</script> 可允许的生成函数定理 <script type="math/tex">\small(\rm The\ admissibility\ theorem\ for\ ordinary\ generating\ functions)</script>
</h4>
<p>在本节中主要归纳上面的基本构造与生成函数的关系。</p>
<p><strong>定理 <script type="math/tex">\mathbf I.1</script></strong> (无标号)：并集、笛卡儿积、序列、幂集、多集和循环的构造都是允许的。公式如下面给出：
<script type="math/tex; mode=display">
\begin{aligned}
\text{并集}:&\mathcal{A}=\mathcal B+\mathcal C&\Longrightarrow& A(z)=B(z)+C(z)\\
\text{笛卡尔积}:&\mathcal{A}=\mathcal B\times\mathcal C&\Longrightarrow& A(z)=B(z)\cdot C(z)\\
\text{序列}:&\mathcal{A}=\mathrm{SEQ}(\mathcal B)&\Longrightarrow&A(z)=\frac1{1-B(z)}\\
\text{幂集}:&\mathcal{A}=\mathrm{PSET}(\mathcal B)&\Longrightarrow&A(z)=\begin{cases}\displaystyle\prod_{n\ge1}(1+z^n)^{B_n}\\\displaystyle\exp\left(\sum_{k=1}^\infty\frac{(-1)^{k-1}}{k}B(z^k)\right)\end{cases}\\
\text{多重集}:&\mathcal{A}=\mathrm{MSET}(\mathcal B)&\Longrightarrow&A(z)=\begin{cases}\displaystyle\prod_{n\ge1}(1-z^n)^{-B_n}\\\displaystyle\exp\left(\sum_{k=1}^\infty\frac1{k}B(z^k)\right)\end{cases}\\
\text{环}:&\mathcal A=\mathrm{CYC}(\mathcal B)&\Longrightarrow&A(z)=\sum_{k=1}^\infty\frac{\varphi(k)}{k}\ln\frac1{1-B(z^k)}
\end{aligned}
</script>
对于序列、幂集、多重集、环，假定 <script type="math/tex">\mathcal{B}_0=\varnothing</script>。</p>
<p>中立类与原子类的 <script type="math/tex">\mathbf{OGF}</script> 再来复读一遍：
<script type="math/tex; mode=display">
E(z)=1,Z(z)=z
</script>
<strong>证明</strong>：下面我们将要一步一步证明上面的公式。</p>
<h5 id="_3">组合和</h5>
<p>组合和与笛卡尔积上面都证明过了，写的比较简略。</p>
<p>令 <script type="math/tex">\mathcal{A}=\mathcal{B}+\mathcal{C}</script>
<script type="math/tex; mode=display">A(z)=\sum_{\alpha\in\mathcal A}z^{|\alpha|}=\sum_{\alpha\in\mathcal B}z^{|\alpha|}+\sum_{\alpha\in\mathcal{ C}}z^{|\alpha|}=B(z)+C(z)</script>
</p>
<h5 id="_4">笛卡尔积</h5>
<p>令 <script type="math/tex">\mathcal{A}=\mathcal{B}\times\mathcal{C}</script>
<script type="math/tex; mode=display">A(z)=\sum_{\alpha\in\mathcal A}z^{|\alpha|}=\sum_{(\beta,\gamma)\in(\mathcal{B}\times\mathcal C)}z^{|\beta|+|\gamma|}=B(z)\cdot C(z)</script>
</p>
<h5 id="_5">序列构造</h5>
<p>序列的定义是从 和 和 笛卡尔积中定义的。记 <script type="math/tex">\mathcal A=\mathrm{SEQ}(\mathcal B)</script>
<script type="math/tex">(\mathcal{B}_0=\varnothing)</script>，有：
<script type="math/tex; mode=display">
\mathcal{A}=\{\epsilon\}+\mathcal{B}+(\mathcal{B}\times\mathcal{B})+(\mathcal{B}\times\mathcal{B}\times\mathcal{B})+\ldots
</script>
就有：
<script type="math/tex; mode=display">A(z)=1+B(z)+B^2(z)+B^3(z)+\ldots=\frac1{1-B(z)}</script>
</p>
<h5 id="_6">幂集构造</h5>
<p>首先令 <script type="math/tex">\mathcal B</script> 为一个有限集合，<script type="math/tex">\mathcal A=\mathrm{PSET}(\mathcal B)</script> 则
<script type="math/tex; mode=display">
\tag{21}{\mathrm{PSET}(\mathcal B)\cong\prod_{\beta\in\mathcal B}(\{\epsilon\}+\{\beta\})}
</script>
<script type="math/tex">\epsilon</script> 是一个大小为 <script type="math/tex">0</script> 的中立类。然后就写成生成函数的形式：
<script type="math/tex; mode=display">
\tag{22}{
A(z)=\prod_{\beta\in\mathcal B}(1+z^{|\beta|})=\prod_{n}(1+z^n)^{B_n}
}
</script>
把众所周知 <script type="math/tex">\exp+\ln</script> 可以把积式写成和式。
<script type="math/tex; mode=display">
\tag{23}{
\begin{aligned}
A(z)&=\exp(\sum_{n=1}^\infty B_n\log(1+z^n)) \\
&=\exp(\sum_{n=1}^\infty B_n\cdot\sum_{k=1}^\infty(-1)^{k-1}\frac{z^{nk}}k)\\
&=\exp(\sum_{k=1}^\infty(-1)^{k-1}\frac{\sum_{n=1}^\infty B_nz^{nk}}k)\\
&=\exp(\sum_{k=1}^\infty(-1)^{k-1}\frac{B(z^k)}k)\\
&=\exp(\frac{B(z)}1-\frac{B(z^2)}2+\frac{B(z^3)}3+\ldots)
\end{aligned}
}
</script>
众所周知对数可以展开：
<script type="math/tex; mode=display">\log(1+u)=\frac u1-\frac{u^2}2+\frac{u^3}3+\ldots</script>
交换求和顺序应该是常规操作了。
上面的结果证明 <script type="math/tex">\mathcal A_n</script> 只于 <script type="math/tex">\mathcal B_j(j\le n)</script> 有关。 </p>
<p>因此 <script type="math/tex">\mathcal B</script> 可以是无限集合。</p>
<h5 id="_7">多重集构造</h5>
<p>记 <script type="math/tex">\mathcal B</script> 为有限集合 <script type="math/tex">(\mathcal{B}_0=\varnothing)</script>，<script type="math/tex">\mathcal A=\mathrm{MSET}(\mathcal B)</script> 为其所构成的多重集，那么有：
<script type="math/tex; mode=display">
\tag{24}{
\mathrm{MSET}(\mathcal B)\cong\prod_{\beta\in\mathcal B}\mathrm{SEQ}(\{\beta\})
}
</script>
换句话说，任意的多重集可以看做是有序的若干 <script type="math/tex">\beta_1</script> ,若干 <script type="math/tex">\beta_2\ldots</script>，也就是变成 <script type="math/tex">\{\epsilon,(\beta_1),(\beta_1,\beta_1),\ldots\}\times\{\epsilon,(\beta_2),(\beta_2,\beta_2),\ldots\}\times\ldots</script>，也就是：
<script type="math/tex; mode=display">
\tag{25}{
\begin{aligned}
A(z)&=\prod_{\beta\in\mathcal B}\frac1{1-z^{|\beta|}}=\prod_{n=1}^\infty(1-z^n)^{-B_n}\\
&=\exp(\sum_{n=1}^\infty-B_n\log(1-z^n))\\
&=\exp(\sum_{n=1}^\infty-B_n\sum_{k=1}^\infty\frac{-z^{kn}}k)\\
&=\exp(\sum_{k=1}^\infty\frac{B(z^k)}k)\\
&=\exp(\frac{B(z)}1+\frac{B(z^2)}2+\frac{B(z^3)}3+\ldots)
\end{aligned}
}
</script>
仍然是 <script type="math/tex">\exp-\ln</script> 的套路，</p>
<h5 id="_8">环构造</h5>
<p>换构造可能是最难的一个，因此放到最后。首先变换 <script type="math/tex">\mathcal A=\mathrm{CYC}(\mathcal B)</script> 就会有：
<script type="math/tex; mode=display">
A(z)=\sum_{k=1}^\infty\frac{\varphi(k)}k\log\frac1{1-B(z^k)}
</script>
<script type="math/tex">\varphi(x)</script> 是欧拉函数。如果 <script type="math/tex">L_k(z)\coloneqq \log(1-z^k)^{-1}</script>
</p>
<p>现在还不能证明，先放一放。
<script type="math/tex; mode=display">
A(z)=\frac11L_1(z)+\frac12L_2(z)+\frac23L_3(z)+\frac24L_4(z)+\frac45L_5(z)+\frac26L_6(z)+\ldots
</script>
</p>
<blockquote>
<p>
<script type="math/tex">\mathbf I.7</script>
<script type="math/tex">\rm Vallee’s identity</script> (不知道怎么翻译)：如果 <script type="math/tex">\mathcal M=\mathrm{MSET}(\mathcal C)</script> ，<script type="math/tex">\mathcal P=\mathrm{PSET}(\mathcal C)</script>，那么
<script type="math/tex; mode=display">M(z)=P(z)M(z^2)</script>
事实上硬推必定能推出来，但是不优美。<script type="math/tex">M(z^2)</script> 强制选偶数个 <script type="math/tex">P(z)</script> 每个数可奇可偶，乘起来对应可以可偶 <script type="math/tex">M(z)</script>
</p>
</blockquote>
<h5 id="smallrmrestricted-constructions">限制构造<script type="math/tex">\small\rm(Restricted\ constructions)</script>
</h5>
<p>为增强构造的能力，我们希望能限制元素数量。设 <script type="math/tex">\mathcal K</script> 是 <script type="math/tex">\mathrm{SEQ, CYC, MSET, PSET}</script> 中的一种，而 <script type="math/tex">\Omega</script> 是一个约束条件，记 <script type="math/tex">\mathcal K_\Omega(\mathcal A)</script> 为满足约束的 <script type="math/tex">\mathcal K</script> 构造。例如：</p>
<p>
<script type="math/tex; mode=display">
\tag{26}\mathrm{SEQ}_{=k}(\text{or}\ \mathrm{SEQ}_k),\mathrm{SEQ}_{>k},\mathrm{SEQ}_{1,\ldots,k}
</script>
</p>
<p>分别指组件个数等于 <script type="math/tex">k</script>，大于 <script type="math/tex">k</script>，在 <script type="math/tex">[1,k]</script> 的序列。</p>
<p>可以发现：
<script type="math/tex; mode=display">
\begin{aligned}
&\mathrm{SEQ}_k(\mathcal B)\coloneqq\overbrace{\mathcal B\times\ldots\times\mathcal B}^{k\text{次}}\equiv\mathcal B^k\\
&\mathrm{SEQ}_{\ge k}(\mathcal B)=\sum_{j\ge k}\mathcal B^j\cong \mathcal B^k\times\mathrm{SEQ}(\mathcal B)\\
&\mathrm{MSET}_k(\mathcal B)\coloneqq \mathrm{SEQ}(\mathcal B)/\mathbf{R}
\end{aligned}
</script>
同样的，<script type="math/tex">\mathrm{SEQ}_{odd},\mathrm{SEQ}_{even}</script> 分别代表奇数个和偶数个。</p>
<p>恰好为 <script type="math/tex">k</script> 个的 <script type="math/tex">\mathrm{SEQ}_k</script> 是比较好推的。
<script type="math/tex; mode=display">
\tag{27}{
\mathcal A=\mathrm{SEQ}_k(\mathcal B)\Longrightarrow A(z)=B(z)^k}
</script>
</p>
<h4 id="mathbf-i23-smallrmconstructibility-and-combinatorial-specifications">
<script type="math/tex">\mathbf I.2.3</script> 可构造性和组合规范 <script type="math/tex">\small\rm(Constructibility\ and\ combinatorial\ specifications)</script>
</h4>
<p>我们希望用规范的语言来描述未标记类的符号方法。</p>
<p>首先我们可以通过基本构造重新审视 <script type="math/tex">\mathbf I.1</script> 中的例题：
<script type="math/tex; mode=display">
\boxed{
\begin{aligned}
&\mathcal W=\mathrm{SEQ}(\mathcal A)\quad\mathrm{where}\quad\mathcal A=\{a,b\}\cong\mathcal Z+\mathcal Z\\
&\mathcal N=\mathrm{CYC}(\mathcal Z+\mathcal Z)\quad \mathrm{and}\quad \mathcal I=\mathrm{SEQ}_{\ge1}(\mathcal Z)\\
&\mathcal P=\mathrm{SEQ}(\mathcal I)\equiv\mathrm{SEQ}(\mathrm{SEQ}_{k\ge1}(\mathcal Z))
\end{aligned}
}
</script>
正整数的多重集与整数排列同构，因此可以得到 <script type="math/tex">\mathcal P</script>，具体内容参见 <script type="math/tex">\mathbf I.3</script>。 </p>
<p>正如例子所展示的一样，一个规范的迭代可以通过 <script type="math/tex">\mathcal E,\mathcal Z,+,\times,\mathrm{SEQ},\mathrm{PSET},\mathrm{MSET},\mathrm{CYC}</script> 通过一系列构造定义出来。</p>
<p><strong>递归的语义</strong><script type="math/tex">\rm(Semantics\ of\ recursion)</script> ：接下来我们将注意力转向递归规范。从树形结构开始。</p>
<p>从图论 <del>以及OI常识</del> 得到，树是无环的无向图。如果钦定一个节点，树就变成了有根树。接下来讨论的树称之为 <strong>平面树</strong> <script type="math/tex">(\rm  plane )</script>，因为这棵树在平面上，子树是有顺序的。定义 <script type="math/tex">\mathcal G</script> 是这类树的类，一棵树的大小定义为 节点的个数。例如下图给出了一棵大小为 <script type="math/tex">16</script> 的树。</p>
<p><img alt="" src="/img/h4pxsgr8.png"></p>
<p>在当前的定义下，如果交换第二棵子树与第三棵子树，得到的树是不等价的，也即子树有序。</p>
<p>树的图像定义是不难得到的，但树同样可以线性定义。一棵树 <script type="math/tex">\zeta</script> 一个根和子树 <script type="math/tex">\tau_1,\ldots,\tau_r</script>，记做 <script type="math/tex">\zeta\  \boxed{\tau_1,\ldots,\tau_r}</script>。由于先前强调过子树有序，因此一个框 <script type="math/tex">\boxed{\cdot}</script> 可以看做是多元组 <script type="math/tex">(\cdot)</script>。这样我们就可以得到一个线性描述。因此树最好用递归来描述，先是一个根，然后接若干棵有序的子树。也就是：
<script type="math/tex; mode=display">
\mathcal G=\mathcal Z\times\mathrm{SEQ}(\mathcal G)
</script>
<script type="math/tex">\mathcal Z</script> 就是一个孤零零的 <script type="math/tex">\{\bullet\}</script> 原子类。</p>
<p>例如 <script type="math/tex">\mathcal G^{[1]}=\mathcal Z\times\mathrm{SEQ}(\varnothing)=\{(\bullet,\epsilon)\}\cong\{\bullet\}</script>：
<script type="math/tex; mode=display">
\mathcal G^{[2]}=\{\bullet,\bullet\boxed{\bullet},\bullet\boxed{\bullet\bullet},\bullet\boxed{\bullet\bullet\bullet},\ldots\}\\
\mathcal G^{[2]}=\{\bullet,\bullet\boxed{\bullet},\bullet\boxed{\bullet\bullet},\bullet\boxed{\bullet\bullet\bullet},\ldots\\
\bullet\boxed{\bullet\boxed{\bullet}},\bullet\boxed{\bullet\boxed{\bullet\bullet}},\bullet\boxed{\boxed{\bullet\bullet}\bullet},\bullet\boxed{\bullet\boxed{\bullet\bullet}\boxed{\bullet\bullet},\ldots}
\}\\
</script>
<script type="math/tex">\mathcal G^{[j]}</script> 代表深度不超过 <script type="math/tex">j</script> 的类。每个 <script type="math/tex">\mathcal G^{[j]}</script> 都具有很好的定义，因为是纯粹通过迭代得到的。并且有 <script type="math/tex">\mathcal G^{[j]}\subset \mathcal G^{[j+1]}</script>。记 <script type="math/tex">\mathcal G</script> 为 <script type="math/tex">\mathcal G^{[j]}</script> 的极限即 <script type="math/tex">\mathcal G\coloneqq{\Large{\cup}}_{j}\mathcal G^{[j]}</script>。</p>
<blockquote>
<p>
<script type="math/tex">\mathbf I.7</script> 类的上确界 <script type="math/tex">\rm (Lim\!-\!sup\ of\ classes )</script>。如果有一个递增组合类序列 <script type="math/tex">\{\mathcal A^{[j]}\}</script> 使得 <script type="math/tex">\mathcal A^{[j]}\subset \mathcal A^{[j+1]}</script> 并且大小的计算方式相同，<script type="math/tex">\mathcal A^{[\infty]}={\Large\cup}_j\mathcal A^{[j]}</script> 的每个大小的元素都是有限的，那么在形式拓扑学中的 <script type="math/tex">\mathbf {OGF}</script> 满足 <script type="math/tex">A^{[j]}(z)=\lim_{j\to\infty}A^{[j]}(z)</script>。</p>
</blockquote>
<p><strong>定义 <script type="math/tex">\mathbf I.7</script></strong> ：<script type="math/tex">\vec{\mathcal A}=(\mathcal A)^{(1)},\ldots,\mathcal A^{(r)})</script> 的<script type="math/tex">r</script>元组的规范 <script type="math/tex">\rm(A\ specification\ for\ an\ r\!–\!tuple )</script>  是一个方程的集合：
<script type="math/tex; mode=display">
\tag{29}{
\begin{cases}
\mathcal A^{(1)} &=& \Phi_1(\mathcal A)^{(1)},\ldots,\mathcal A^{(r)})\\
\mathcal A^{(2)} &=& \Phi_2(\mathcal A)^{(1)},\ldots,\mathcal A^{(r)})\\
&\ldots&\\
\mathcal A^{(r)} &=& \Phi_r(\mathcal A)^{(1)},\ldots,\mathcal A^{(r)})\\
\end{cases}
}
</script>
每个 <script type="math/tex">\Phi_i</script> 表示通过 <script type="math/tex">\mathcal E,\mathcal Z,+,\times,\mathrm{SEQ},\mathrm{PSET},\mathrm{MSET},\mathrm{CYC}</script> 进行的操作。</p>
<p>我们称该系统为 <script type="math/tex">\mathcal A^{(1)}</script> 的规范。 组合类的规范是该类的一种形式语法。如果 <script type="math/tex">(29)</script> 中的系统是严格上三角的，那么它是一个迭代或非递归的规范，也就是说 <script type="math/tex">\mathcal A^{(r)}</script> 仅由初始类 <script type="math/tex">\mathcal Z,\mathcal E</script> 定义。而 <script type="math/tex">\mathcal A^{(r-1)}</script> 只与 <script type="math/tex">\mathcal A^{(r)} </script> 有关，最终 <script type="math/tex">\mathcal A^{(1)}</script> 必定可以通过 <script type="math/tex">\mathcal Z,\mathcal E</script> 表示出。</p>
<p>否则这个系统就是递归的。类似树的方法，从空的向量开始迭代，<script type="math/tex">\vec{\mathcal A}^{[0]}=(\varnothing,\ldots,\varnothing)</script>，<script type="math/tex">\vec{\mathcal A}^{[j+1]}=\vec{\Phi}[\vec{\mathcal A}^{[j]}]</script>。</p>
<p>有另一种更方便的形象化的方法，给定一个 <script type="math/tex">(29)</script> 的规范，我们可以将其依赖关系图 <script type="math/tex">\Gamma</script> 关联到它。<script type="math/tex">\Gamma</script> 的顶点集是引索集合 <script type="math/tex">\{1,\ldots,r\}</script>。对于每个等式 <script type="math/tex">\mathcal A^{(i)}=\Xi_i(\mathcal A^{(1)},\ldots,\mathcal A^{(r)})</script> ,若 <script type="math/tex">\mathcal A^{(j)}</script> 在等式的右侧，那么在 <script type="math/tex">\Gamma</script> 中连接一条有向边 <script type="math/tex">(i\to j)</script>。</p>
<p>如果一个类的依赖关系是迭代的，那么图 <script type="math/tex">\Gamma</script> 必然无环。若存在有向环那么就是递归关系。</p>
<p><strong>定义</strong> <script type="math/tex">\mathbf I.8</script> ：如果一个组合结构可以通过和、积、序列、幂集、多重集和循环构造一个规范，那么它就是可构造或可指定的。</p>
<p>因此现在，我们得到了一种组合结构的规范语言，它是集合理论的一部分添加了递归。根据 <strong>定理</strong> <script type="math/tex">\mathbf I.1</script> ，每个可构造类都有一个普通生成函数，可以系统地生成泛函方程。甚至可以用计算机系统地计算它。</p>
<p><strong>定理 <script type="math/tex">\mathbf I.2</script></strong>(符号化的、无标号)：一个可构造类的生成函数是函数方程组的组成部分，其项是由下面的东西建立的：
<script type="math/tex; mode=display">
1,z,+,\times,Q,\mathrm{Exp},\overline{\mathrm{Exp}},\mathrm{Log}
</script>
更具体地有：
<script type="math/tex; mode=display">
\boxed{
\begin{aligned}
&Q[f]=\frac1{1-f}&,&\mathrm{Log}[f]=\sum_{k=0}^\infty \frac{\varphi(k)}k\log\frac1{1-f(z^k)}\\
&\mathrm{Exp}[f]=\exp\left(\sum_{k=1}^\infty\frac{f(z^k)}k\right)&,&
\overline{\mathrm{Exp}}[f]=\exp\left(\sum_{k=1}^\infty(-1)^{k-1}\frac{f(z^k)}k\right)
\end{aligned}
}
</script>
<strong>Pólya操作</strong> <script type="math/tex">\rm(Pólya\  operators)</script>：操作 <script type="math/tex">Q\rm (sequences,SEQ)</script> 也被称之为 <strong>拟逆</strong> <script type="math/tex">\rm( quasi\!-\!inverse )</script> 。操作 <script type="math/tex">\mathrm{Exp}(\mathrm{multisets},\mathrm{MSET})</script>被称之为 Pólya级数 <script type="math/tex">\rm(Pólya\   exponential)</script>，<script type="math/tex">\overline{\mathrm{Exp}}(\rm powersets,PSET)</script> 是修改过的Pólya级数 <script type="math/tex">\rm( modified\ Pólya\ exponential)</script>。<script type="math/tex">\mathrm{Log}\rm(cycle,CYC)</script> 称之为 Pólya对数 <script type="math/tex">\rm(Pólya\  logarithm )</script>。简而言之 Pólya 牛逼。</p>
<p>上面的 <strong>定理 <script type="math/tex">\mathbf I.2</script></strong> 说明迭代类有生成函数，且只涉及基本运算的组合。递归结构可以通过方程组间接访问 <script type="math/tex">\mathbf{OGF}s</script>。</p>
<p>接下来我们将看到一些符号方法说明：</p>
<hr>
<p><strong>二进制单词</strong>：二进制单词的 <script type="math/tex">\mathbf{OGF}</script> 很容易看出：
<script type="math/tex; mode=display">
\mathcal W=\mathrm{SEQ}(\mathcal Z+\mathcal Z)\quad\Longrightarrow\quad W(z)=\frac1{1-2z}
</script>
最后的结果得到 <script type="math/tex">W_n=2^n</script>。在我们的框架中，如果 <script type="math/tex">a,b</script> 是不同的字母，那么 <script type="math/tex">\mathcal Z+\mathcal Z\cong \{a,b\}</script>
</p>
<hr>
<p><strong>一般树</strong>：一般树的递归规范使得它们的 <script type="math/tex">\mathbf{OGF}</script> 的隐式定义：
<script type="math/tex; mode=display">
\mathcal G=\mathcal Z\times\mathrm{SEQ}(\mathcal G)\quad\Longrightarrow\quad G(z)=\frac z{1-G(z)}
</script>
从现在开始就可以用基础代数了。在形式幂级数环上原方程等价于 <script type="math/tex">G-G^2-z=0</script>。这个方程可以通过  <script type="math/tex">\mathrm{radicals}</script> 求解：
<script type="math/tex; mode=display">
\begin{aligned}
G(z)&=\frac12\left(1-\sqrt{1-4z}\right)\\
&=x + x^{2} + 2 x^{3} + 5 x^{4} + 14 x^{5} + 42 x^{6} + 132 x^{7} + 429 x^{8}+\ldots\\
&=\sum_{n\ge1}\frac1n\binom{2n-2}{n-1}z^n
\end{aligned}
</script>
另一个根直接舍掉了，因为系数出现负数、常数项不为 <script type="math/tex">0</script>。</p>
<p>展开用的是牛顿二项式展开：
<script type="math/tex; mode=display">
(1+x)^{\alpha}=1+\frac a1x+\frac{a(a-1)}{2!}x^2+\ldots
</script>
把 <script type="math/tex">\alpha=\frac12</script>，<script type="math/tex">x=-4z</script> 带入即可。</p>
<p>我们还发现：
<script type="math/tex; mode=display">
\tag{30}{
C_n=\frac1{n+1}\binom{2n}n\quad\mathrm{with}\ \mathbf{OGF}\quad C(z)=\frac{1-\sqrt{1-4z}}{2z}
}
</script>
这就是我们熟知的卡特兰数。因此一般树可以用卡特兰数枚举：
<script type="math/tex; mode=display">
G_n=C_{n-1}=\frac1n\binom{2n-2}{n-1}
</script>
</p>
<hr>
<p><strong>三角形剖分</strong>：凸 <script type="math/tex">n+2</script> 边形逆时针标上 <script type="math/tex">0,\ldots,n+1</script>，分成 <script type="math/tex">n</script> 个三角形称之为三角形剖分，大小为三角形的个数，即 <script type="math/tex">n</script>。为了方便计数，我们钦定一个包含 <script type="math/tex">0,1</script> 的三角形为根，那么就可以分成一个根三角形与两个子三角形剖分：</p>
<p><img alt="" src="/img/qjfzsa33.png"></p>
<p>如果定义 <script type="math/tex">\mathcal T</script> 三角形剖分的类，就有：
<script type="math/tex; mode=display">
\mathcal T=\{\epsilon\}+(\mathcal T\times\triangledown \times \mathcal T)
</script>
考虑到我们认为 <script type="math/tex">2</script> 边形三角形的个数为 <script type="math/tex">0</script>，因此 <script type="math/tex">\mathbf{OGF}\ T(z)</script> 满足方程：
<script type="math/tex; mode=display">
\tag{31}{
T(z)=1+zT(z)^2\Longrightarrow T(z)=\frac1{2z}(1-\sqrt{1-4z})
}
</script>
作为 <script type="math/tex">(30)</script> 和 <script type="math/tex">(31)</script> 的结果，三角形划分用卡特兰数枚举：
<script type="math/tex; mode=display">
T_n=C_n=\frac1{n+1}\binom{2n}n
</script>
</p>
<blockquote>
<p>
<script type="math/tex">\mathbf I.9</script> 一个双射：既然普通树与三角形划分都能用卡特兰数枚举，那么必然存在一个双射。</p>
<p>
<script type="math/tex">\mathbf I.10</script> 三角形划分的一种变体。让 <script type="math/tex">\mathcal U</script> 是非空的划分构成的类，即 <script type="math/tex">\mathcal U=\mathcal T/\{\epsilon\}</script>，就会有：
<script type="math/tex; mode=display">\mathcal U=\triangledown+(\triangledown\times \mathcal U)+(\mathcal U\times \triangledown)+(\mathcal U\times\triangledown\times\mathcal U)</script>
同样我们可以得到 <script type="math/tex">U(z)=(1-2z-\sqrt{1-4z})/(2z)\equiv T(z)-1</script>
</p>
</blockquote>
<h4 id="mathbf-i24-smallrmexploiting-generating-functions-and-counting-sequences">
<script type="math/tex">\mathbf I.2.4</script> 利用生成函数和计数序列 <script type="math/tex">\small\rm(Exploiting\ generating\ functions\ and\ counting\ sequences)</script>
</h4>
<p>在这本书中，我们将看到符号方法的一百多个应用（害怕）。在进一步深入前，有必要说一说如何更好地利用生成函数和计数序列来解决组合问题。</p>
<h5 id="smallrmexplicit-enumeration-formulae">显式枚举公式 <script type="math/tex">\small\rm(Explicit\ enumeration\ formulae)</script>
</h5>
<p>在许多情况下 生成函数是显式的，并且可以通过某种神秘的方式展开，得到他们的系数，上面的一般树和三角形剖分就是很好的例子。由 <script type="math/tex">\mathbf{OGF}</script> 满足的方程也可以得到显式解，然后用牛顿二项式定理展开。类似地，后面推导了一个通过符号方法得到整数组合数的显式形式，并通过 <script type="math/tex">\mathbf{OGF}</script> 得到相关结果。在这本书中，我们假定大家都会从小学二年级的基本微积分中获得的基本技巧，并得到一个显式函数的泰勒展开式。</p>
<h5 id="smallrmimplicit-enumeration-formulae">隐式枚举公式 <script type="math/tex">\small\rm(Implicit\ enumeration\ formulae)</script>
</h5>
<p>在许多情况下，用符号法得到的母函数在某种意义上任然是显式的，但它们的形式是这样，不能化为封闭的形式。然而有可能通过符号操作系统获取相应的计数序列的初始值。此外，通过生成函数，可以系统地推导出递归，从而得出以合理有效的方式计算计数序列中任意数量项的过程。比如下面一个经典的例子，整数分区的 <script type="math/tex">\mathbf{OGF}</script>：
<script type="math/tex; mode=display">
\prod_{m=1}^\infty \frac1{1-z^m}
</script>
这个将在后面证明满足方程：
<script type="math/tex; mode=display">
H(z)=z\exp\left(H(z)+\frac12H(z^2)+\frac13H(z^3)+\ldots\right)
</script>
系数可以通过较低的复杂度计算。</p>
<h5 id="smallrmasymptotic-formulae">渐进公式 <script type="math/tex">\small\rm(Asymptotic\ formulae)</script>
</h5>
<p>这样的形式是我们的终极目标，因为他们允许对计数序列进行简单的解释和比较，增长速度因该是 <script type="math/tex">W<T<P</script>。计数序列的增长率属于组合结构的渐进理论，通过复分析与符号方法有很好的联系。后文会有详细的阐述。无论符号法提供的母函数多么复杂，几乎都可以渐进估计其系数。也就是说，渐进方法很好地涵盖了上述的隐式枚举。</p>
<p>那么如何严谨地比较增长快慢呢？</p>
<p>我们用 <script type="math/tex">\sim</script> 表示大约相等，那么：
<script type="math/tex; mode=display">
n!\sim n^ne^{-n}\sqrt{2\pi n}
</script>
这是一个非常牛逼的渐近公式，因为不仅与自然对数 <script type="math/tex">e</script> 有关，还与圆周率 <script type="math/tex">\pi</script> 有关。这就是著名的斯特林公式。换句话说：
<script type="math/tex; mode=display">
\tag{32}{n!=\left(\frac ne\right)^n\sqrt{2\pi n}\left(1+O\left(\frac1n\right)\right)\quad (n\to+\infty)}
</script>
在本书中给了好几种证明，等看到再说。这里有一张精确值与斯特林数比值的表格：</p>
<table>
<thead>
<tr>
<th>
<script type="math/tex">n</script>
</th>
<th>
<script type="math/tex">1</script>
</th>
<th>
<script type="math/tex">2</script>
</th>
<th>
<script type="math/tex">5</script>
</th>
<th>
<script type="math/tex">10</script>
</th>
<th>
<script type="math/tex">100</script>
</th>
<th>
<script type="math/tex">1000</script>
</th>
</tr>
</thead>
<tbody>
<tr>
<td>
<script type="math/tex">n!/(n^ne^{-n}\sqrt{2\pi n})</script>
</td>
<td>
<script type="math/tex">1.0844376</script>
</td>
<td>
<script type="math/tex">1.0422071</script>
</td>
<td>
<script type="math/tex">1.016784</script>
</td>
<td>
<script type="math/tex">1.0083654</script>
</td>
<td>
<script type="math/tex">1.0008337</script>
</td>
<td>
<script type="math/tex">1.0000833</script>
</td>
</tr>
</tbody>
</table>
<p>误差是真的小，非常牛逼的说。</p>
<p>可以用斯特林公式推卡特兰数的渐近形式：
<script type="math/tex; mode=display">
C_n=\frac1{n+1}\frac{(2n!)}{(n!)^2}\sim\frac 1n\frac{(2n)^{2n}e^{-2n}\sqrt{4\pi n}}{n^{2n}e^{-2n}2\pi n}
</script>
可以简写为：
<script type="math/tex; mode=display">
\tag{33}{C_n\sim\frac{4^n}{\sqrt{\pi n^3}}}
</script>
因此卡特兰数的增长大致相当于 <script type="math/tex">4^n</script>，由次指数因子调制。这个渐近估计后面还有用。总之，用一个简单（？）的公式可以很好地总结出一般树和三角形剖分的渐近数目。这三个序列的增长大概是长这样的：</p>
<p><img alt="" src="/img/q9qgp2bz.png"></p>
<p>我们若记 <script type="math/tex">C^*_n</script> 为估计出来的卡特兰数，那么其值越来越接近。 <del>因为不知道怎么算，就不给表了。</del> 还是附一张原书上的图罢：</p>
<p><img alt="" src="/img/960nq57c.png"></p>
<p>这样的渐近公式是序列的增长率之间的比较容易。</p>
<p>组合结构与渐近结构之间的相互作用是本书讨论的重点，将在 <script type="math/tex">\mathrm{Part.B}</script> 看到。由符号方法提供的母函数通常可以简单渐近系数估计。</p>
<blockquote>
<p>
<script type="math/tex">\mathbf I.11</script> 编码的复杂度。如果有一个公司声称可以最多用 <script type="math/tex">1.5n</script> 位储存空间对大小 <script type="math/tex">n\ge100</script> 的任何三角形剖分编码，你会做什么？</p>
<p>
<script type="math/tex">\mathbf I.12</script> 根据上面一张图估计 <script type="math/tex">C^*_{10^7}/C_{10^7}</script> 与 <script type="math/tex">C^*_{5\cdot 10^6}/C_{5\cdot10^6}</script>，精确到 <script type="math/tex">25</script> 位数字。</p>
</blockquote>
<h3 id="mathbf-i3-smallrminteger-compositions-and-partitions">
<script type="math/tex">\mathbf I.3</script> 整数组合与划分 <script type="math/tex">\small\rm(Integer\ compositions\ and\ partitions)</script>
</h3>
<p>本节和接下来几个小节提供了在组合理论的经典领域中通过我们刚刚的规范进行计数的例子。它们说明了符号化的好处：生成函数几乎不需要任何计算，同时，从基本的组合结构中可以得到许多计算的改进。这里描述的最直接的应用涉及到整数分解，用分区和组合的经典组合-算数结构。这些规范是迭代的，并且简单地结合类型 <script type="math/tex">\mathrm{SEQ,MSET,CYC,PSET}</script> 的两层结构。</p>
<h4 id="mathbf-i31-smallrmcompositions-and-partitions">
<script type="math/tex">\mathbf I.3.1</script> 组合和划分 <script type="math/tex">\small\rm(Compositions\ and\ partitions)</script>
</h4>
<p>我们的第一个例子是把整数分解成和。</p>
<p><strong>定义 <script type="math/tex">\mathbf I.9</script></strong>：整数 <script type="math/tex">n</script> 的组合是一个整数序列 <script type="math/tex">(x_1,x_2,\ldots,x_k)</script> 满足
<script type="math/tex; mode=display">
n=x_1+x_2+\ldots+x_k,x_j\ge1
</script>
它的划分是一个整数序列 <script type="math/tex">(x_1,x_2,\ldots,x_k)</script> 满足：
<script type="math/tex; mode=display">
n=x_1+x_2+\ldots x_k,x_1\ge x_2\ge\ldots\ge x_k\ge 1
</script>
在两种情况下，<script type="math/tex">x_i</script> 被称为<strong>和式</strong><script type="math/tex">(\rm summands)</script> 或 <strong>部分</strong><script type="math/tex">(\rm parts)</script>，<script type="math/tex">n</script> 是大小。</p>
<p>通过小圆点 <script type="math/tex">\bullet</script> 表示在一元空间中求和，那么画成条形图就可以和组合和分区有联系了：
<script type="math/tex; mode=display">
\begin{aligned}
&\quad\begin{matrix}
\\
\\
\\
\bullet
\end{matrix}
\begin{matrix}
\\
\bullet\\
\bullet\\
\bullet
\end{matrix}
\begin{matrix}
\\
\\
\\
\bullet
\end{matrix}
\begin{matrix}
\bullet\\
\bullet\\
\bullet\\
\bullet
\end{matrix}
\begin{matrix}
\\
\\
\bullet\\
\bullet
\end{matrix}
\begin{matrix}
\\
\bullet\\
\bullet\\
\bullet
\end{matrix}\\\\
&\bullet|\bullet\bullet\bullet|\bullet|\bullet\bullet\bullet\bullet|\bullet\bullet|\bullet\bullet\bullet
\end{aligned}
</script>
上图就展示了一个组合大小为 <script type="math/tex">1+3+1+4+2+3=14</script>。类似地阶梯形可以表示划分。就不用 <script type="math/tex">\LaTeX</script> 画图了大家自己理解就好（</p>
<p>设 <script type="math/tex">\mathcal C</script> 和 <script type="math/tex">\mathcal P</script> 分别表示所有组合和划分构成的类。由于集合总是可以以顺序的方式呈现，因此组合与划分的区别在于和式的顺序是否重要。这反映在序列构造和多集构造的使用上。从这个角度看，把 <script type="math/tex">0</script> 看做是由空的和序列 <script type="math/tex">(k=0)</script> 是很方便的，我们现在也就这么做：</p>
<p><strong>整数类</strong> <script type="math/tex">\small\rm(Integers, as\ a\ combinatorial\ class)</script>：令 <script type="math/tex">\mathcal I=\{1,2,\ldots\}</script> 为所有整数的组合类，并以每个整数的大小为这个元素的大小，<script type="math/tex">\mathcal I</script> 的 <script type="math/tex">\mathbf{OGF}</script> 是很容易得到的：
<script type="math/tex; mode=display">
\tag{34}{
I(z)=\sum_{n\ge1}z^n=\frac z{1-z}
}
</script>
因为当 <script type="math/tex">n\ge1</script> 时 <script type="math/tex">I_n=1</script>，对应的是，对于每个大小为 <script type="math/tex">n\ge 1</script> 的对象，<script type="math/tex">\mathcal I</script> 中只有一个整数与它对应。如果整数是用一元表示的，比如小球，那么有：
<script type="math/tex; mode=display">
\tag{35}{
\mathcal I=\{1,2,3,\ldots\}\cong\{\bull,\bull\bull,\bull\bull\bull\}=\mathrm{SEQ}_{k\ge1}\{\bull\}
}
</script>
这就给出了一个直观的方法来形象化等式 <script type="math/tex">I(z)=\frac z{1-z}</script>
</p>
<p><strong>组合</strong>：首先根据 <strong>定理 <script type="math/tex">\mathbf I.1</script></strong>，组合作为序列对象可以直接翻译成 <script type="math/tex">\mathbf{OGF}</script>：
<script type="math/tex; mode=display">
\tag{36}{
\mathcal C=\mathrm{SEQ}(\mathcal I)\Longrightarrow C(z)=\frac1{1-I(z)}
}
</script>
结合公式 <script type="math/tex">(34)</script> 与 <script type="math/tex">(36)</script>，就可以完全确定 <script type="math/tex">C(z)</script>：
<script type="math/tex; mode=display">
\begin{aligned}
C(z)&=\frac1{1-\frac z{1-z}}=\frac{1-z}{1-2z}\\
&=1+z+2z^2+4z^3+8z^4+16z^5+\ldots
\end{aligned}
</script>
在这里，组合的计数问题可以直接展开 <script type="math/tex">\mathbf {OGF}</script> 来求解：
<script type="math/tex; mode=display">
C(z)=\left(\sum_{n\ge0}2^nz^n\right)-\left(\sum_{n\ge0}2^nz^{n+1}\right)
</script>
即 <script type="math/tex">C_0=1,C_n=2^n-2^{n-1}</script>，就是：
<script type="math/tex; mode=display">
C_n=2^{n-1},n\ge1
</script>
这是比较形式化与符号化得做法，如果是常规做法就是 <script type="math/tex">n</script> 个小球之间有 <script type="math/tex">n-1</script> 个空隙，在中间摆木棒，显然方案数为 <script type="math/tex">2^{n-1}</script>。</p>
<p><strong>划分</strong>：一个划分可以被看做是多重集，根据定理 <script type="math/tex">\mathbf I.1</script> ：
<script type="math/tex; mode=display">
\tag{38}{
\mathcal P=\mathrm{MSET}(\mathcal I)\Longrightarrow P(z)=\exp\left(I(z)+\frac12I(z^2)+\frac13I(z^3)+\ldots\right)
}
</script>
当然也可以直接用 <script type="math/tex">(25)</script>：
<script type="math/tex; mode=display">
\tag{39}{
\begin{aligned}
P(z)&=\prod_{m=1}^\infty\frac1{1-z^m}\\
&=(1+z+z^2+\ldots)(1+z^2+z^4+\ldots)(1+z^3+z^6+\ldots)\\
&=1+z+2z^2+3z^3+5z^4+7z^5+11z^6+15z^7+22z^8+\ldots
\end{aligned}
}
</script>
这个序列可以在 <a href="https://oeis.org/A000041"><script type="math/tex">\mathbf{OEIS}</script></a> 上找到。与用显式 <script type="math/tex">2^{n-1}</script> 计算的 <script type="math/tex">C_n</script> 不同，<script type="math/tex">P_n</script> 不存在简单的形式。基于鞍点法与 <script type="math/tex">\mathbf{OGF}</script> 的渐近分析表明 <script type="math/tex">P_n=e^{O\left(\sqrt{n}\right)}</script> 。事实上还有更牛逼的渐近：
<script type="math/tex; mode=display">
\tag{40}{
P_n\sim \frac1{4n\sqrt{3}}\exp\left(\pi\sqrt{\frac {2n}3}\right)
}
</script>
因此划分比组合少得多，如下图所示：</p>
<p><img alt="" src="/img/nosi9w4v.png"></p>
<p>这个速度明显差多了好吗。</p>
<blockquote>
<p>
<script type="math/tex">\mathbf I.13</script>
<strong>划分数的递归性</strong> ：对数微分得到：</p>
<p>
<script type="math/tex; mode=display">z\frac{P^\prime(z)}{P(z)}=\sum_{n=1}^\infty\frac{nz^n}{1-z^n}\quad \mathrm{implying}\quad nP_n=\sum_{j=1}^n\sigma(j)P_{n-j}</script>
</p>
<p>式中的 <script type="math/tex">\sigma(n)</script> 指的是 <script type="math/tex">n</script> 的约数和。 这样计算是<script type="math/tex">P_1,P_2,\ldots,P_N</script>
<script type="math/tex">O(N^2)</script> 的。在后面可以降低到 <script type="math/tex">O(n\sqrt{n})</script>。</p>
<p>说句闲话，用多项式科技可以做到 <script type="math/tex">O(n\log n)</script>
</p>
</blockquote>
<p>通过改变 <script type="math/tex">(36)</script> 和 <script type="math/tex">(38)</script> 我们可以使用符号方法以一种简单的方式导出许多计数结果。首先，我们提出以下命题。</p>
<p><strong>命题 <script type="math/tex">\mathbf I.1</script></strong>：让 <script type="math/tex">\mathcal T\subseteq \mathcal I</script> 是一个正整数集的子集，那么类 <script type="math/tex">\mathcal C^{\mathcal T}\coloneqq \mathrm{SEQ}(\mathrm{SEQ}_{\mathcal T}(\mathcal Z))</script>，<script type="math/tex">\mathcal P\coloneqq \mathrm{MSET}(\mathrm{SEQ}_{\mathcal T}(\mathcal Z))</script> 分别指由 <script type="math/tex">\mathcal T\subset \mathbb Z_{\ge 1}</script> 构成的组合和划分：
<script type="math/tex; mode=display">
C^{\mathcal T}(z)=\frac1{1-\sum_{n\in\mathcal T}z^n}=\frac1{1-T(z)}\quad P^{\mathcal T}=\prod_{n\in\mathcal T}\frac1{1-z^n}
</script>
<strong>证明</strong>：根据规范和 <strong>定理 <script type="math/tex">\mathbf I.1</script></strong> 就不难得到。</p>
<p>这个命题允许我们用有限的和以及固定数量的部分来枚举组合和划分。</p>
<p><strong>例题 <script type="math/tex">\mathbf I.4</script></strong> 求有限制的组合。为了枚举从 <script type="math/tex">\{1,2\}</script> 中选取构成的类 <script type="math/tex">\mathcal C^{\{1,2\}}</script> ，只需写：
<script type="math/tex; mode=display">
\mathcal C^{\{1,2\}}=\mathrm{SEQ}(\mathcal I^{\{1,2\}})\quad\mathrm{with}\quad \mathcal I=\{1,2\}
</script>
那么生成函数就是：
<script type="math/tex; mode=display">
C^{\{1,2\}}(z)=\frac1{1-I^{\{1,2\}}(z)}\quad\mathrm{with}\quad I^{\{1,2\}}=z+z^2
</script>
那么就有：
<script type="math/tex; mode=display">
C^{\{1,2\}}(z)=\frac1{1-z-z^2}=1+z+2z^2+3z^3+5z^4+8z^5+13z^6+\ldots
</script>
这个类中 <script type="math/tex">n</script> 的组合数量用斐波那契数表示：
<script type="math/tex; mode=display">
C_{n}^{\{1,2\}}=F_{n+1}\quad\text{where}\quad F_n=\frac1{\sqrt5}\left[\left(\frac{1+\sqrt5}2\right)^n-\left(\frac{1-\sqrt5}2\right)^n\right]
</script>
这个序列的增长被记为 <script type="math/tex">\varphi^n</script>，其中 <script type="math/tex">\varphi</script> 是黄金分割比。</p>
<p>同样地，可以计算所有的都在集合 <script type="math/tex">\{1,\ldots,r\}</script> 的组合的生成函数：
<script type="math/tex; mode=display">
\tag{41}{
C^{\{1,\ldots,r\}}(Z)=\frac1{1-z-z^2-\ldots-z^r}=\frac1{1-z\frac{1-z^r}{1-z}}=\frac{1-z}{1-2z-z^{r+1}}
}
</script>
相应的计数是广义斐波那契数。双组合和表示这些计数：
<script type="math/tex; mode=display">
\tag{42}{
C_n^{\{1,\ldots,r\}}=[z^n]\sum_{j}\left(\frac{z(1-z^r)}{1-z}\right)^j=\sum_{j,k}(-1)^k\binom jk\binom{2-rk-1}{j-1}
}
</script>
</p>
<p>当 <script type="math/tex">n</script> 变大时，这个结果对于分析序列的增长速度没有什么用，因此需要进行渐近分析。若 <script type="math/tex">r\ge2</script>，在<script type="math/tex">\left(\frac12,1\right)</script> 存在唯一根 <script type="math/tex">\rho_r</script> 。在后面表明，对于某些常数 <script type="math/tex">c_r>0</script>，
<script type="math/tex; mode=display">
\tag{43}{
C_n^{\{1,\ldots,r\}}\sim c_r\rho_r^{-n}
}
</script>
当 <script type="math/tex">r=2</script> 时 <script type="math/tex">\rho_r</script> 的作用类似于黄金分割比。</p>
<blockquote>
<p>
<script type="math/tex">\mathbf I.14</script> 拆分成素数。 整数加性分解依然是个谜，例如是否每个偶数都是两个素数的和（哥德巴赫猜想）时未知的。然而， <script type="math/tex">n</script> 的素数组合的个数为 <script type="math/tex">B_n=[z^n]B(z)</script>，</p>
<p>
<script type="math/tex; mode=display"> \begin{aligned}B(z)&=\left(1-\sum_{p\in prime}z^p\right)^{-1}=\left(1-z^2-z^3-z^5-z^7-z^{11}-\ldots\right)^{-1}\\&=1+z^2+z^3+z^4+3z^5+2z^6+6z^7+6z^8+10z^9+16z^{10}+\ldots\end{aligned}</script>
</p>
<p>在 <a href="https://oeis.org/A023360"><script type="math/tex">\mathbf{OEIS}</script></a> 上同样可以找到。</p>
</blockquote>
<p><strong>例题 <script type="math/tex">\mathbf I.5</script></strong> 求有限制的分区。当被限制在有限集合时，这种特殊的分区结果被称为 <script type="math/tex">\rm denumerants</script>。<script type="math/tex">\rm Pólya</script> 提出力一个数数问题：用 <script type="math/tex">1</script> 美分，<script type="math/tex">5</script> 美分，<script type="math/tex">10</script> 美分和 <script type="math/tex">25</script> 美分，找到恰好 <script type="math/tex">99</script> 美分的方法。（取硬币的顺序无关既要，允许重复。）对于有限 <script type="math/tex">\mathcal T</script> 的情况，我们从命题 <script type="math/tex">\mathbf I.1</script> 知道 <script type="math/tex">P^{\mathcal T}(z)</script> 是一个有理函数，并且 <script type="math/tex">P^{\mathcal T}_n</script> 满足一个与 <script type="math/tex">\mathcal T</script> 有关的线性递归。原来问题的解决方法是：
<script type="math/tex; mode=display">
[z^{99}]\frac1{(1-z)(1-z^5)(1-z^{10})(1-z^{25})}=213
</script>
同样我们可以证明：</p>
			</div>
			<div class="panel panel-default card" style="padding: 10px;height: 50px;font-size: 20px;">
				<a style="float: left;" href="\article\P7470.html"><i class="fa fa-angle-double-left"></i></a><a style="float: right;" href="\article\CF848E.html"><i class="fa fa-angle-double-right"></i></a>
			</div>
			<div class="panel panel-default card" style="padding: 10px;font-size: 20px;" id="vcomments">
				
			</div>
			<script>
				new Valine({
					el: '#vcomments',
					appId: 'PAlFUPg0pQVTFTEo8gCB4BCf-gzGzoHsz',
					appKey: 'U38ejnLUiizJ6vLyp6ql4hRq',
					path: window.location.pathname
				})
			</script>
		</div>
		<div class="col-md-3">
				<div class="panel panel-default card">
				<div class="panel-heading">
					<h3 class="panel-title">
						<i class="fa fa-info"></i>&emsp;
						<strong>文章信息</strong>
					</h3>
				</div>
                <div style="margin: 10px;">
                    <div style="margin-top: 8px;display: flex;"> 
    <span style="flex: 1 0 auto;margin-right: 6px;">标题</span>
    <span><font style="font-weight: bold">分析组合 选读</font></span>
	</div><div style="margin-top: 8px;display: flex;"> 
    <span style="flex: 1 0 auto;margin-right: 6px;">日期</span>
    <span>2021-03-21 18:28:41</span>
	</div>
                </div>
				</div>
				<div class="panel panel-default card">
				<div class="panel-heading">
					<h3 class="panel-title">
						<i class="fa fa-tag"></i>&emsp;
						<strong>标签</strong>
					</h3>
				</div>
				<div style="margin: 10px;">
					<a href="/tags/2021/" class="tag"><span  style="background-color: rgb(52, 152, 219);">2021</span></a>&nbsp;<a href="/tags/组合/" class="tag"><span  style="background-color: rgb(231, 76, 60);">组合</span></a>&nbsp;<a href="/tags/笔记/" class="tag"><span  style="background-color: rgb(82, 196, 26);">笔记</span></a>
				</div>
				</div>
				
			<div class="panel panel-default card">
					<div class="panel-heading">
						<h3 class="panel-title">
							<i class="fa fa-user-circle-o"></i>&emsp;
							<strong>caijicjl</strong>
						</h3>
					</div>
					<div style="width: 60%;display: inline-block;padding-top: 10px;">
						<ul class="propertyLinks" style="list-style-type: none;">
							<li>
								<img style="vertical-align:middle;position:relative;top:-2px" src="/img/rating-16x16.png">
								Rating:&nbsp;
								<span style="font-weight:bold;color: gray ">312</span>
							</li>
							<li>
								<img style="vertical-align:middle;position:relative;top:-2px" src="/img/star_blue_16.png">
								Contribution:&nbsp;
								<span style="color:gray;font-weight:bold;">0</span>
							</li>
						</ul>
						<ul class="nav-links">
							<li><a href="/settings/">Settings</a></li>
							<li><a href="/archives/">Blog</a></li>
							<li><a href="/teams">Teams</a></li>
							<li><a href="/submissions/dingdingsb">Submissions</a></li>
							<li><a href="/usertalk">Talks</a></li>
							<li><a href="/contests/with/dingdingsb">Contests</a></li>
						</ul>
					</div>
					<div style="display:inline-block;vertical-align: top;margin: 10px;text-align: center;">
						<div style="height:50px;width:50px"><img src="/img/avatar.png"/></div>
						<div><a href="https://www.luogu.com.cn/user/174304" style="font-weight:bold;color:gray">caijicjl</a></div>
					</div>
				</div>
		<div class="panel panel-default card">
				<div class="panel-heading">
					<h3 class="panel-title">
						<i class="fa fa-external-link"></i>&emsp;
						<strong>画中画</strong>
					</h3>
				</div>
				<div style="width:100%;margin:10px">
				<input type="text" id="url"/>
				<input value="创建" type="button" onclick="creat('kk')" /> 
				</div>
		</div>
		<script src="/js/hitokoto.js"></script>
							

				
				<span id="kk"></span>
				<div  id="myScrollspy" class="card" style="width: 100%;"  data-spy="affix">
					<script src="/js/make_toc.js"></script>
				</div>
		</div>
	</div>
 </div>
</body>
</html>
